package io.github.hadyang.leetcode.algo;

import java.util.Arrays;
import org.junit.Test;

/** @author haoyang.shi */
public class HeapSort {

  @Test
  public void test() {
    int[] nums = {4, 5, 1, 6, 2, 7, 3, 8};
    heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }

  public void heapSort(int[] nums) {
    for (int i = nums.length - 1; i >= 0; i--) {
      maxHeap(nums, 0, i);

      swap(nums, 0, i);
    }
  }

  private void maxHeap(int[] heap, int start, int end) {
    if (start == end) {
      return;
    }

    int parent = start;
    int childLeft = start * 2 + 1;
    int childRight = childLeft + 1;

    if (childLeft <= end) {
      maxHeap(heap, childLeft, end);

      if (heap[childLeft] > heap[parent]) {
        swap(heap, parent, childLeft);
      }
    }

    if (childRight <= end) {
      maxHeap(heap, childRight, end);

      if (heap[childRight] > heap[parent]) {
        swap(heap, parent, childRight);
      }
    }
  }

  private void swap(int[] nums, int a, int b) {
    int t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
  }
}
